
\documentstyle[bk11,dina4]{article}

\hbadness=2500     \vbadness=3500
\clubpenalty9500   \widowpenalty9500
\tolerance=9999    \spaceskip=0.38em plus 0.3em minus 1pt

\textheight=22cm
\footskip=3\baselineskip
\hyphenation{ }

\newcommand{\yeah}{$\stackrel{^\circ \imath ^\circ}{_\smile}$}



\begin{document}


\title{	EPO ~V\,0.5\\
	 The evolutionary parameter optimizer \\
	shareware manual }

\author{ (C) 4/94 ~~ Petra Roosen\\
	Petra\_Roosen$@$ac3.maus.de }

\date{\today}

\maketitle

\begin{abstract}

As a universal parameter optimization program EPO is applicable to almost any problem. It is based on an evolutionary algorithm derived from the biological paradigm of evolution theory. It does not require, for its work, insights into the mathematical background of the system to be optimized. Instead, an implicit model of the dependencies is built up during a run, evaluating the success and failure of exploring steps. Therefore EPO is able to co-operate with a great number of (so far) isolated simulation programs that don't have to be designed for optimization purposes.

The underlying evolutionary algorithm increases the stability and the convergence security compared to deterministic-based optimization systems. Therefore EPO is strongly recommended for difficult problems, especially.

In this shareware version up to 5 parameters may be dealt with. The full version can treat many more, and is limited essentially by RAM size only. Custom made versions for specialized problems, that cannot be covered with the scheme presented in EPO but would suggest evolutionary approaches, are available on request.

EPO needs a multi-tasking operating system. The version included is compiled for OS/2 personal computers; a unix version is evaluated at the moment and will be ported to a variety of platforms.

(No, there will be no DOS version!)

\end{abstract}

\newpage

\tableofcontents

%=======================================================

\vspace*{2cm}

\section{Evolutionary optimization for technical problems}

\subsection{General survey of optimization techniques}

To be able to use a thing or a method, it must serve its purpose it was designed for in an appropriate measure. The fitness of newly developed products usually improves gradually with time, due to the competition in the market by rivalling products. Facing this, we are almost arriving at the topic this program system is about, although in a somewhat different context.

This improvement of functionality, called optimization from now on, can be gained by different ways of approach:
%
\begin{itemize}
	\item The developer of a new product brilliantly looks through the underlying context and just chooses the best way to get things done. This kind of optimization is always aimed at but rather seldom found. (If your problem can be dealt with in such a way, don't fuss around with this program and do it!)
	\item A prototype is constructed at first. Improvements in detail are stepwise realized. This should be the method applied mostly.
	\item The system behaviour is simulated, and the mathematical representation allows an analytical determination of the best parameter constellation. Simplest examples are the (in-)famous minimum-maximum problems of the upper school classes.
	\item In spite of mathematical modeling of the problem, there is no analytical solution to be found, perhaps, because the function to be optimized cannot be disintegrated for analytical treatment. This situation encountered in many practical cases necessitates the application of searching methods. Usually they are derived from the analytical paradigm, that is: in a small neighborhood around the spot in parameter space just investigated, an analytical treatment is supposed to yield good results with respect to the global aim. Such methods are commonplace in operations research and the general treatment of optimization problems. You won't have any difficulty in finding lots of textbooks about them.
	\item An analytical treatment is dispensed, a stochastical approach is used instead. This is commonly used if the fitness function has several sub-optimal regions or depends in a difficult way on the determining parameters. In such cases the analytically derived optimization tools have grave problems in finding good solutions, as practical people will readily assure you.\\
A special class of methods copies the procedures encountered in nature. Various paradigms are employed, beginning at the ``simulated annealing'' derived from the physics of solidification~\cite{ Otto:SimAn} and leading to the ideas taken from the biology of species development~\cite{ Rieck:ModellNatur, Schwef:Opti}.
\end{itemize}

The basic algorithm  of EPO is based on such a evolutionary paradigm usually called ``evolution strategy''. It is strongly dominated by the notions of ``(random) mutation'' and ``(deterministic) selection'', as will be explained down below.

In the present form it needs a problem definition that can be treated by calculator application, although there have been applications reported, where this paradigm was applied to practical, experimental optimization, too~\cite{ Rechen:Evolut}.



\subsection{Underlying ideas of evolutionary optimization}

Before I describe the practical work with EPO down below, let me shortly discuss the fundamental ideas of evolutionary computing and its difference compared to conventional, analytically based optimization techniques.

The biological organisms have developed in quite a fascinating way during the last millions of years --- originating in rather simple forms but gradually moving to higher and higher complexity. Although complexity usually goes with error rate in technical systems, biological systems seem to contradict this rule: there is no technical system nearly as complex as even the simplest forms of biological creatures, but the functionality of them is thoroughly remarkable.

Complexity and functionality of biological entities have led many to the conclusion that the world has been {\em created\/} by a higher being. In fact a combinatorial analysis shows that the probability to bring together a human genetic set just by throwing dice is practically nill in scientific terms.

This way of explanation and judgement is insensible, though: Every genetic set differs from any other, and all beings are doing more or less well in everyday life. So there is no need to reproduce just {\em one\/} special set of genes to obtain a working copy of a biological being. Many alternatives will do --- more or less well.

Since the first formulation of the evolution theory by Darwin the notion of a theory of a constant {\em development\/} of species has become commonplace. There is not much doubt about its correctness nowadays since a lot of evidence has been found supporting it. Together with developental physiology and genetics a consistent paradigm has grown to explain the diversity of our present world~\cite{ Hoppe:Biophysik}.

According to this model of explanation the development of biological systems is due to evolution, that is: due to testing of new variants of creatures departing only in small details compared to their ancestors. There is a constant, immediate, competition with respect to the slightly different designs of the same species, and an indirect one towards other living beings. Natural selection will take care that mainly those, being the fittest in this struggle of life, will reproduce best and carry on their genetic material, thus spreading it in the population.

In a simplifying model the genetic set of an individual can be interpreted as the determining information to rule the fitness of the being. While this should be quite a good approximation for the lower species, it is not as true for the more complex biologic systems. Here the information inherited by learning from the ancestors and the individual experience and training must not be forgotten.

However, since even the simplest biological forms are well above the complexity of our technical apparatuses, we might forget those higher forms of individual improvement and, for starters, concentrate on the porting of the underlying genetic development metaphor to technical systems.

This idea was pursued by various authors in the late sixties. Two main directions can be distinguished: while in the anglo-american area Holland introduced the {\em Genetic Algorithms\/} based on bit-string representation of the technical ``genes'', resembling the biological DNA coding, in Germany Rechenberg, Schwefel, and others~\cite{ Kursaw:Vektor, Handelsreis, Schwef:Opti, Schwef:DirectSearch, Schw88, PPSN:1990} developed the so called ``evolutionary strategies'', putting gene sets of real-valued numbers to work.



\subsection{Basic algorithmic structure of the evolution strategy}

According to nature the evoution strategy does not optimize a single instantiation of a technical system, but utilizes a {\em population\/} of those. Such a population consists of {\em individuals\/}, that is: examples of the technical system in question differing in their fitness-determining parameter set, being interpreted as the genome of the individual.

Let me give an example: If I want to minimize the energy costs of a house, I may take a look at the determining parameters I can influence: thickness of walls, choice of materials for walls and windows, heating equipment choice, joint tightness, and, say, choice of roof material. These six parameters form the ``genetic set'' for an individual construction concept, being interpreted as one of my individuals, and will yield my fitness function ``energy costs''%
\footnote{Please note that I did not choose the energy {\em consumption\/} as fitness function, since the result of the optimization would be trivial: In any case the best heat-insulating material and the thickest possible structure would be the result. By inclusion of the cost aspect there will be a non-trivial, practically sensible, result: If heat insulation is already good, further material addition will yield not much but costs lots of additional money.}.

The population consists of individuals with different combinations of the parameters, thus yielding different fitness function values. In analogy to a deterministic search step in parameter space, in evolutionary optimization a new {\em generation\/} is formed. The individuals of this new generation are formed by choosing the best $n$ ones of the old generation with respect to the fitness function and mixing pairs of their genetic sets to form $m$ children by a recombination and mutation process resembling the biological one. Please keep in mind, that this mutation and recombination is only stochastic and not aim-oriented!

Depending on the chosen variant of strategy either the parents are removed from the newly-formed population (so-called ``comma strategy'' in the german terminology), or they parents are kept and compete their childern in the next generation (called ``plus strategy'').

Even if it seems dubious to throw away successes once achieved and replace them with less fit individuals, it usually showed that the comma strategy is the more stable and secure one with respect to convergence quality, especially so if self-adapting step sizes are taken into consideration. Therefore it is the only one implemented in EPO so far%
\footnote{Forthcoming versions of EPO will supply additional strategy variants, including maximum ages and perhaps higher forms of biological metaphors of reproduction techniques.}.

\bigskip

Just a reminder at the end of this paradigm introduction: EPO is neither a sorcering program nor a wonder weapon of practical optimization --- it is just another approach competing with a lot of different, established ones. There will be many cases in which even EPO will not yield the best possible solution, or when the optimization process will simply take too much time to yield a sensible result.

But this is usually not the fault of the program or of its underlying algorithm, but the insidiousness of the practical problem. Pitily, many of the practical problems are to be placed into this category $\ldots$

There will be a lot of cases in which deterministic optimizers will do a good and fast job. Do not use EPO in this cases, since evolutionary algorithms are well-known to be somewhat slow in progress compared to working deterministic ones. But if the deterministic ones fail (or you don't want to mess around with optimizing deterministic optimizers for good convergence speed), give EPO a chance! Judging from some practical experiences in chemical engineering problems, those cases are quite frequent. 



\subsection{Putting the evolution strategy into a program system}

The momentary parameter values as the ``genetic set'' of the individuals represent the whole information necessary for the determination of their fitness functions. Their initial values are read from a configuration file by the main module, called ``optimizer'' at the beginning of an optimization run. During the run they are worked upon and maintained by the optimizer. This module is also producing the result and progress reports during the run.

The exact strategy may be influenced by a number of strategy parameters, which are also read from a configuration file. Various problem treatments may be tuned by this, especially by doing a trade-off between progress speed and convergence security (especially important for multi-modal problems).

\bigskip

The determination of the fitness function of a given parameter constellation is none of the optimizer's business. Therefore the ``simulator'' part was completely kept out of the optimizer and was placed into a separate module. The information transfer between those two modules is done by the file system via data and message files.

Depending on the given problem there are various ways to tie the simulator to the optimizer:
%
\begin{itemize}
	\item A new program must be written to simulate the system's response to parameter settings:\\
This case is eased by a simulator template included in the packet. The complete communication handling between optimizer and simulator is read-to-use, only the problem-dependent part must be supplied by the user in a subroutine. To do so, all parameter names and present values are accessible in arrays.
	\item There is a ready-to-use batch simulator for the problem in question at hand:\\
In this case the existing simulator usually requires custom call conventions (e.g.\ the submission of prepared data files, command parameters). Again there is a template included in the packet to demonstrate this simulator type inclusion in a practical example. The template supplies the communication to the optimizer and gives access to parameter values and names. The external simulator custom preparation is done only in a given subroutine range, as demonstrated in the example.
\end{itemize}

The practical work with these system components will be explained in detail in the sections \ref{Arbeitsweise} and \ref{Praxis}.



\section{System components}

Although literature reports on various implementations of evolutionary algorithms for technical optimization~\cite{ Doerin:Filter, Muelle:EvoBeisp,  Schmie:Mikrowelle}, there is, to my knowledge, no generally applicable program system to be fitted to differing problem cases. This is what EPO is made for.

To achieve a simple adaption to various and differing problems, EPO was designed modularly. The shareware version contains all modules of the full version, in order to show the flexibility and potence of the system. Only the number of parameters to be treated in a given optimization run was limited to five in the shareware version.

The system was designed to treat (almost) any simulatable problem as long as the operating system of the performing computer allows a simultaneous running of the optimizer and the simulator. For personal computers I chose the OS/2 system, being very potent to support long-running, heavy-duty, background processes due to its pre-emptive multitasking. Presently the system is ported to unix platforms and will be available on an number of systems soon%
\footnote{Accordingly, you will find dedicated versions of EPO on various FTP servers soon. If you need EPO on a currently unsupported machine, please give me a call --- e-mail addresses see above or below!}.

To introduce practical optimization work, EPO includes ready-to-use problem cases serving as confidence testing of the installed system. Section~\ref{Praxis} will explain in detail how to treat individual problems with the given set of templates. You will need a certain experience in programming, since a pre-defined software interface must be obeyed for communication between optimizer and problem-dependent simulator. But this has been stereotyped as much as possible, so you can mainly concentrate on the problem implementation.

Main part of EPO is the program SHOPTI.EXE%
\footnote{SHOPTI.EXE is the name of the OS/2 version. Corresponding Unix executables will be named accordingly, following the name conventions of the given systems. Descriptions given for the OS/2 version will hold for the Unix variants, too, unless differences are specifically pointed out.}. %
It has to be created by a ``rename'' from the file SHOPTI.BIN.

I have to admit this procedure is somewhat mean. But I beg your pardon I chose it this way in order to make you read this manual, since I do not believe anyone can do anything with EPO without reading it first. I wanted to prevent senseless fiddling around with the binaries by making you read these instructions.

SHOPTI.EXE is the evolutionary optimizer and the real kernel of the system, doing the whole control and generating the reports on progress and success.

As stated before, the shareware version of EPO only serves five parameters. This is a restriction of functionality, shure, but before everyone now shouts ``crippleware'': There are quite a lot of rather difficult optimization problems in spite of their low number of variables, being a real challenge to the handling programs. In any case, this version should be able to give insight into the potential of the method. (And last but not least, I would like to earn some money with EPO, therefore needing some incentive for you to get into contact with me.)

\bigskip

The program SIMU.EXE has to be created in the same way, by renaming SIMU.BIN. It is the counterpart of SHOPTI.EXE and is a complete simulation program: the multi-dimensional quadratic function of a set of variables is calculated in the problem-dependent part and returned to the optimizer as the fitness function to be minimized.

The source for this module is also included in EPO as SIMU.C. You can take it as a source code template to formulate your own problem definition by replacing the custom problem-dependent computing subroutine, while the communication handling is taken care of by the rest of the template's code.

For access to the parameter values, see the given example and, if you need the parameter names, too, take a look at the data structures in the header and the handling in the communication section.

\bigskip

The binding to completely independent simulation programs needs the serving of their parameter handling peculiarities. Basically, this can be dealt with again by modifying SIMU.C. In order to ease this task I included an additional template called TRANS.C (Once again: rename TRANS.BIN). The formulated example herein addresses the independent ``simulator'' GAUSSFIT.EXE (yes, you already guessed it $\ldots$) which calculates the error square sum of a gaussian fitted set of ``experimental'' measurement values. GAUSSFIT.EXE needs five command line parameters for invocation:
%
\begin{enumerate}
	\item Name of the file consisting of the measurement point set defined by entries of the form \{x value, y value\} per row. Maximum number of entries are 99. You find an example measurement file named REIN in the packet.
	\item Height of the proposed fitting curve.
	\item Mean value of the proposed fitting curve.
	\item Mean deviation of the proposed fitting curve.
	\item Name of the desired output file wherein GAUSSFIT.EXE places (among other output) the calculated error square sum.
\end{enumerate}

This somewhat exotic simulator call should be an appropriate example for treating externals. It is served by TRANS.* by supporting the necessary program call, and extracting the wanted output information from the GAUSSFIT output file to pass it on to the optimizer.

\bigskip

The work of the optimizer is controlled by two further files: STRATEG.DAT and CONDITIO.DAT. Their structure will be discussed in the sections below.

Since EPO was compiled with the emx compiler, the file EMX.DLL is mandatory somewhere in the libpath. I included this file, too, even though it is not an integral part of EPO. If you have already a sufficiently new copy of it, just throw away the one distributed in this package.

During runs of EPO further files are generated, whose names and meaning will be discussed below. They are not large (temporary files typically $<$ 2 kB, result files $<$ 200 kB) and should pose no problem to usual hard disc capacities.



\section{Short course of EPO usage}
\label{Arbeitsweise}

\subsection{General course of an optimization run}

In general the procedure of an optimizing run is always the same. First the simulator module has to be connected to the optimizer via a defined data interface, e.g.\ by explicit formulation of the calculating subroutine in SIMU.C, or by explicitly invoking an external simulator by defining the parameter transfer via re-adjustment of the corresponding TRANS.C subroutine.

Next, the boundary conditions of the run are to be defined in the steering files, as will be explained in the following sections.

\bigskip

After these preliminaries are finished, the optimizer is started by a double-click on the icon or typing the command in a command line processor. The optimizer reports by a copyright notice and prints out the data read from the steering files.

The optimizer invokes the desired simulator, as was defined in the steering files, as an additional process. Thus, the simulator window may be observed in parallel, and may be used to control the actions therein by user-defined printouts into the window.

After a successfull start of the whole system the progress is reported in the optimizer window. For every generation the desired number of best individuals is displayed. The absolute best value and the generation, in which it was found is also displayed.

Data files are exchanged among optimizer and simulator modules for every individuum to be calculated. Two files are used for every direction: one containing the actual data (O2S.DAT or S2O.DAT, depending on the direction) and one acting as a message file (*.MSG) to make shure the data file is closed by the writer and valid for reading%
\footnote{There seem to exist several conditions in multitasking operating systems (both OS/2 and Unix) when data files are {\em not\/} valid altough the message file is written not sooner than after the data file has been closed by the writing program. This effect was observed especially when transferring rather large data file (several kB). To circumvent problems with that, a simple read control has been introduced in addition to the EPO 0.1 packet. It sets a pausing time adaptively to minimize encountered read errors, but (luckily) usually is not activated.}. %
The message files do not have any contents, only the existence of their name is important.

The optimizer may be stopped interactively by pressing ``q'' in its active window. Since this input is no sooner evaluated than a single simulator run has returned, the actual stop of the process may be delayed shortly. Don't get impatient, please!

The unix version cannot accept a keyboard interrupt for the optimizing task after it has been pushed to background operation and the system was left intermittently by the user. Therefore the optimizer is looking for a file named ``stop'' as an interrupt request. It can be created by entering ``touch stop'' via a command line, but make shure to create the file in the correct subdirectory --- the one the optimizer is regarding as working directory.

If the optimizer is stopped with this regular method, the simulator is stopped automatically, too, and the temporary transfer files are erased. The file system is left clean.

If you cannot wait for the simulator to finish its run or encounter an error condition, you may stop either program manually, usually by entering $<$Ctrl-C$>$ in the respective window. In this case you have to clean up the file system by yourself. I strongly recommend to do so, since left-over transfer files can disturb the next optimization run, e.g. by causing an offset between the submitted parameter data and the appearingly received fitness value for that set. Furthermore a remaining message file can lead to the momentary stopping of the simulator.

The optimization results are documented in two files that will be discussed in section~\ref{strateg.dat}.



\subsection{The CONDITIO.DAT control file}
\label{conditio}

The File CONDITIO.DAT contains the information necessary to define the number and initial values of the variables to be treated, as well as explicit definition range boundaries.

\bf
ATTENTION: Due to the very simple scanning system of these input data implemented in EPO~0.5 you need to reproduce the complete input structure in the correct syntax. There is no automatical validation whether the read data are correct!
\rm

The data is read in with the simple string or number input routines of the C language. Thus, the number of whitespace between the entries is not important, but the correct amount of data items is. You can supervise the input as it is read by the optimizer by watching the control output in the optimizer window during its start.

A typical file contents may be the following (no line numbers in the original, of course --- included here just for the matter of explanation):

\begin{verbatim}
1:   Exampe-1
2:   Para_number   3
3:   Name       Value   L.Limit   U.Limit
4:   Variable1  20      -1        50.45
5:   Variable2  13.5    -5        25
6:   Variable3  -4.3    -10       25.4
\end{verbatim}

Line 1 carries the name of the problem to be treated (one word without a space!). It will be read and used as a header line in the output report files.

Line 2 begins with a marker word for the number of parameters to be optimized (word is not read) and the actual number. This number of lines is scanned for inputs after $\ldots$

The headings of the columns in line 3 are skipped. You must leave them in your input file, though, and use them as a reminder for the sense of the individual entries.

Lines 4 to 6 finally carry the parameter entries. The first column consists of the parameter names (single words!), the second of the initial values. Third and fourth column take the lower and upper limit of the definition ranges respectively. If a parameter should be unbounded, take sufficiently large positive and negative numbers.

Please remember that the shareware version of EPO will only treat up to five parameters. You may enter more, but only the first five will be accepted.



\subsection{The STRATEG.DAT control file}
\label{strateg.dat}

STRATEG.DAT carries information necessary for the optimizer control: simulator name, population layout, some internal evolution strategy settings, and transfer file and directory specifications.

\bf
ATTENTION: Due to the very simple scanning system of these input data implemented in EPO~0.5 you need to reproduce the complete input structure in the correct syntax. There is no automatical validation whether the read data are correct!
\rm

Again, the data is read in with the simple string or number input routines of the C language. Thus, the number of whitespace between the entries is not important, but the correct amount of data items is. You can supervise the input as it is read by the optimizer by watching the control output in the optimizer window during its start.

A typical file contents may be the following (again, no line numbers in the original, of course):

\begin{verbatim}
 1: EPO-0.5
 2: minimize
 3: simulator_name     simu
 4: optidelay          400
 5: individual_number  30
 6: best               5
 7: inbreeding         1
 8: display            5
 9: result_file        Erg1.out
10: history_file       Gra1.out
11: transfer_dir       g:\
12: tau0               0.3
13: tau1               2
14: init_var         0.1
15: auto_stop          300
\end{verbatim}

Line 1 carries the word EPO-0.5 as an indicator for the control file of the correct EPO version.

Line 2 can consist of the key words ``maximize'' or ``minimize'' Accordingly the optimization will take the given direction.

On line 3 the desired simulator or mediator is to be defined after the keyword. It will be automatically started by the optimizer. The name has to be defined as it would be entered manually for a simulator start. (Again, only a one-word entry is allowed!) Usually you just have to put the simulator's name here, without any additional path, since the simulator usually resides in the same directory as the optimizer.

The entry on line 4 defines the period the optimizer waits after an unsuccessfull attempt to read the simulator's message file, usually due to the fact that the simulator did not come to an end yet. The entry is interpreted as milliseconds%
\footnote{In Unix environment there usually is no millisecond timer, therefore the entry is converted into a second value: e.g.\ 2340~ms $\rightarrow$ 2~s).}. %
It is a senseless waste of calculation time to let the optimizer do futile access to the file system. Even for short-running single simulator runs a wait time of 0.5~s is sensible.

Line 5 specifies the number of individuals in the population, line 6 the number of parents selected to generate the next generation. In the given example 5 individuals will be taken as parents and 25 children will be produced.

Line 7 defines whether the children must result from a true recombination of two parents (inbreeding 0)  or may be produced by mutating just one parent only (inbreeding 1).

Line 8 contains the number of best individuals to be displayed as progress report in the optimizer window for each generation. By defining a larger number you can estimate the residual variety in the present generation, by defining a smaller one you can follow the development over two or three generations in the window.

In line 9 the ``tomb stone'' file name is defined: Here the absolute best parameter constellation of a given optimization run is documented. The entry after the keyword is understood as a complete path definition.

Line 10 has the name of a history file, to be appended every time an absolute improvement has been found. Only generation and fitness value of the best is appended, so a good overview over the optimization development is gained.

Line 11 defines the directory where the transfer files of simulator and optimizer are placed. If you have a RAM disk in your system, use it to speed up the transfer and minimize the load of your physical devices. the given entry is once again interpreted as a complete path.

Lines 12 and 13 contain two control parameters to tune the optimization progress. Usually, values between 0.2 and 2.0 are sensible for both $tau0$ and $tau1$. If you have to compute some lengthy sets of similar structured problems you might play with these entries to get faster convergence. But as usual, speed is traded against security, especially if working on multi-modal problems.

In line 14 the relative measure of the initial variation span is to be defined. The given value is common to all treated variables, as defined in section~\ref{conditio}.

Finally, line 15 contains the maximum number of generations which is allowed not to produce an absolute progress. If this number is reached without any further improvement, the optimizer is stopped automatically and also stops the simulator process.



\section{Confidence testing with included example problems}

A first practical run and insight in the way EPO works you can obtain with the example problems in the packet:

\begin{itemize}
	\item {\bf First example: calculation embedded in simulator --- multi-dimensional minimization of quadratic sums}
	\item Rename all files with extension BIN to EXE (e.g.: \verb+ren *.bin *.exe+)
	\item Take a look at the files CONDITO.DAT and STRATEG.DAT. Try to understand their function with help of the description above. In the example three parameters with a restricted definition range are worked upon. The present directory is chosen as the transfer directory. SIMU(.EXE) is chosen as simulator to be invoked.
	\item start SHOPTI(.EXE)
	\item Watch its window: after the starting notice the read-in parameters are displayed.
	\item In the beginning a parent generation is formed, as you may notice from the printouts.
	\item After that, the continuously repeating loop is entered: Creation of children, submission to simulator, sampling of the fitness results, sorting, displaying the sorted population, writing of the result files if new absolute best values are found.
	\item Stop the run either by pressing ``q'' or leaving the optimizer alone until the maximum allowed number of generations without an absolute improvement has arrived (five generations in the example) and the optimizer stops automatically.
	\item Take a look at the result file (in the example: ERG1.OUT) to find the best setting of parameters. The history file (in the example:  GRA1.OUT) you can recall the development of fitness function values over number of generations: at any absolute improvement a line is added to show generation and new fitness value. Using a data plot program (e.g.\ GnuPlot) you can transform this file in a nice graphical description of optimization progress.
	\item {\bf Second example: call of an external simulator --- GAUSSFIT}
	\item Edit the entry after \verb+simulator_name+ and change it from ``simu'' to ``trans''.
	\item Change the output file entries in order not to overwrite the old ones in the next run.
	\item Re-run the optimizer.
	\item Put the TRANS(.EXE) window in front and watch the control outputs of GAUSSFIT, being displayed in the TRANS window (read-in ``measuring values'', calculated gauss fit values, squared error's sum, finally relative squared error's sum as return value).
	\item Again, watch the optimization progress in the SHOPTI window and stop the run as you desire.
\end{itemize}

At a regular program stop an additional file is written: STATUS.ERG. Here the state of the population at program stop time is documented. This is sometime helpfull for comparison reasons relative to the best values in the result file.



\section{Working with EPO: Adaption to ``real'' problems}
\label{Praxis}

If you want to apply EPO to your real problem you cannot help doing a tiny bit of programming yourself. To minimize this necessary effort, the templates SIMU.C and TRANS.C are included in the packet. They do already all the work as far as communication with the optimizer is concerned and give examples how to handle the rest.

The binary parts of EPO have been compiled and tested with the E.~Mattes emx system. Thus using mainly the underlying Gnu C compiler the transfer of the system to Unix environments has been very simple. In order to simplify this porting, I used only the basic library functions being available on any platform so far.

Of course you can take other compiler systems, but look for the inclusions of the correct libraries and include files, whose names may differ.



\subsection{Programming of a simulator}

Take SIMU.C as a basis of your new simulator module. The hard core of your simulator has to replace the example problem in the subroutine \verb+rechne()+.

The number of parameters to be considered are found in the variable \verb+Parazahl+.

The present parameter values are given via the structure \verb+Indi+ as \verb+Indi.koeff[i]+. The simulator result, the value of the fitness function, must be placed in \verb+Indi.Ergebnis+ on return from the subroutine, so it can be sent back to the optimizer.

There are some further entries in the \verb+Indi+ structure which are initialized by the optimizer, too, but some of them are historical remnants, some will be used in versions to come, e.g.\ for asynchronous multi-simulator control. Therefore do not use those entries for your own purposes, please, since they are subject to change, but hand them back to the optimizer unchanged.

If you need information about the name of a passed parameter you find it in the \verb+Limits[i].Name+ array. The remaining entries of this array are {\em not} initialized.



\subsection{Binding to an external simulator}

If you have already a running simulator to calculate a fitness function of interest, you can modify TRANS.C  to integrate it into the optimization system. Again, the communication between TRANS and SHOPTI is ready-to-use, so you can concentrate on preparing the simulator input data and invocation call. This has to replace the example given in the \verb+rufe()+ subroutine in TRANS.C.

The data structures and the necessary handling of them are the same as in SIMU.C, so please refer to their discussion above.



\section{Debugging}

Due to the rather low fault tolerance of the control data input routines (so far) scanning errors are bound to happen. (Sorry! But if you cannot accept them at present, wait for version 0.5 or so.) Therefore I designed all control and transfer files as simple ASCII files, so you can easily take a look what information is passed between the respective modules.

If the optimizing run does not behave as you expected it, take a look at the read-in data control output first.

If this is correct, start the EPO modules only one at a time. By this you can take a look at the transfer file produced by SHOPTI or SIMU/TRANS respectively. Since SHOPTI starts the simulator module automatically, you have to mis-define the simulator name in STRATEG.DAT in order to take a look at the O2S.DAT transfer file. (Just forget about the error message during the start of SHOPTI, saying it cannot find the simulator.) If this file is as you expected it to be, stop SHOPTI by pressing $<$Ctrl-C$>$ and invoke the simulator alone afterwards. It will take the transfer file as in an ordinary combination run, and will produce the S2O.DAT file, which you now can inspect without the optimizer deleting it at once.

If you stopped your last optimizing production run the hard way (by pressing $<$Ctrl-C$>$ or similar) but did not think about cleaning up the file system, there might be some files hindering proper work the next time you start the complete system. Here is a short overview what file might disturb which program:

\vspace{1cm}

\begin{tabular}{|llll|}
\hline
Programm to test	& necessary		& produces	& disturbed by  \\
\hline
SHOPTI		& STRATEG.DAT	& O2S.DAT	& S2O.DAT\\
			& CONDITIO.DAT	& O2S.MSG	& S2O.MSG\\
			&			& (ERG.OUT)	&	\\
			&			& (GRA.OUT)	&	\\
\hline
SIMU			& STRATEG.DAT	& S2O.DAT	& (wrong O2S.DAT) \\
			& O2S.MSG		& S2O.MSG	&\\
			& O2S.DAT		& 		& \\
\hline
TRANS			& STRATEG.DAT	& S2O.DAT	& (wrong O2S.DAT) \\
			& O2S.MSG		& S2O.MSG	&\\
			& O2S.DAT		& 		& \\
			&			&		& (return file)\\
\hline
\end{tabular}

\vspace{1cm}

Testing SHOPTI the bracketed files are not necessarily produced. With SIMU and TRANS wrong entries in the O2S.DAT lead to immediate program stop. Take a look at the given parameter number in the transfer file: a parameter number of ``0'' is interpreted as stopping condition by the simulator modules.

There is a caveat using TRANS which cannot be helped from this side: The return file sent from the external simulator to TRANS cannot be dealt with automatically from the SHOPTI if the system stops, since there is no information about its name present in the optimizer. Either you have to put in an according program sequence into TRANS.C (find the place where the existence of a stop message from the optimizer is checked and add appropriate statements) or you have to delete the simulator return file manually each time you stop the EPO system.

If you neglect this there will be an offset between the parameter files sent to the simulator and the result files taken by TRANS, leading to the destruction of the \{Parameter set/Fitness\} correlation, and therefore to erratic behavior of the complete optimizing system. This problem basically cannot be solved, since there is no message file controlling the data transfer between simulator and TRANS --- contrary to the interfacing between SHOPTI and TRANS.



\section{Version log and outlook}

EPO version 0.1 was distributed in march 1994 only on a local bbs, and was replaced very soon by version 0.2.

Additions and corrections in EPO 0.2:
\begin{itemize}
	\item Transfer problem by temporary file system inconsistency fixed by checking the correct number of read-in parameters.
	\item Continuous adaptive control of optimizer and simulator wait time until file system consistency is re-established.
	\item Additional definable optimizer wait time between return data ready checks, to minimize unneccessary computing time waste.
	\item Fix of some minor inconsistencies of result file writing.
	\item Additional status file is written after optimizer was normally stopped.
\end{itemize}

EPO 0.3 and 0.4 were internal revisions.

Additions and corrections in EPO 0.5:
\begin{itemize}
	\item Fixed initial variation span formerly defined by definition boundaries replaced by user-defined initial span in STRATEG.DAT, in order to be able to re-start jobs without losing the achieved progress.
	\item Operative Unix version tested on Sparc station.
	\item Automatic removal of ``stop'' file in Unix version.
	\item Fix of some minor beauty (sic!) deficiencies in outputs.
\end{itemize}

\bigskip

The present EPO version 0.5 is a sensibly running system already applicable to real-world problems. I wanted to give it out as soon as possible to get fast response from users to get the development onto practitioner-oriented paths.

Main present point of critique should be the inflexible control data read routines, necessitating great care in preparing the input files. They will be replaced by sensible, more intelligent scanning subroutines assisting the user better.

Next a graphical display of optimization progress will be put in. Presumably this will be done via piping the necessary messages into GnuPlot.

Communication overhead should be minimized by using RAM internal pipes between the modules, instead of files.

Long single simulator runs would benefit strongly from parallelization. This will be built in, too, as EPO data structures are already prepared to support this.

Finally, the man-machine-interface should be optimized. With regard to this aspect EPO~0.5 is way behind even plain DOS, as I shamefully admit. But since optimization is (almost by definition) a batch job best dealt with in a background window, this is one of the last items on the list, presumably the step V0.99 $\rightarrow$ V1.00.



\section{Conditions of use and upgrade registration}

Well, here comes the most unpleasant part of the manual --- but I hope I made it as pleasant as possible for you $\ldots$

As usual for shareware distributions, this packet may be distributed without any limitation as long as it is not changed with regard to its contents. This version (limited to five simultaneously treatable parameters) may be used as long as you like without charge. If EPO is used to produce results of practical importance, I expect its name to be explicitly mentioned in any publication resulting from it. Apart from this I won't fight any voluntary monetary donations which will show me the appreciation for my work and keep my software development going.

An unlimited version (up to several hundreds of parameters, enabling especially the treatment of ordering problems and mixed real/integer problems) is available both for OS/2 and Unix environments. If interested please contact me. Depending on the scope of the problem you should expect license fees in between 150~$ and 1500~$.

Some optimization problems will not fit into the simple architecture demanded by EPO, e.g.\ if special treatment of implicit boundary conditions or a vector optimization is necessary, or the parameters are structured in themselves. For those cases (quite often implying the use of an evolutionary approach) please contact the author who can develop custom fitted optimizers for your special problem!


\newpage

\section*{Acknowledgements}

I would like to thank my brother, Dr.-Ing.\ Peter Roosen, for giving me access to the first internal versions of the evolutionary optimizer on which EPO is based. I hope, by generalizing and consolidating the system, to return him some impulses for his applications in the chemical engineering area.

Big thanks also to Eberhard Mattes, who gave me with his emx C compiler system the opportunity to develop EPO under OS/2. If I had to spend several hundreds of DM for the compiler system this program might not have come into existence.

\bigskip

\noindent
Petra Roosen\\[3mm]
6.4.1994\\



%===================================================================

\newpage
\begin{thebibliography}{99}
\addcontentsline{toc}{section}{Further reading}

\bibitem{ Ablay:SdW} P.\ Ablay: Optimieren mit Evolutionsstrategien; 
Spektrum der Wissenschaft, Juli 1987, 104-114

\bibitem{ Doerin:Filter} J.\ D\"ohring, C.\ H\"alsig: Filterentwurf nach dem Optimierungsprinzip der biologischen Evolution; 26. intern.Wiss.Koll. TH Ilmenau, Vortragsreihe `Schaltungstechnik und elektronische 
Meátechnik',1981

\bibitem{ Eigen:Konvergenz} Global Convergence of Genetic Algorithms: an Infinite Markov Chain Analysis; PPSN, 1990, Dortmund

\bibitem{ HoffHof} U. Hoffmann, H. Hofmann: Einf\"uhrung in die Optimierung; Verlag Chemie, 1971, ISBN 3-527-2534-8

\bibitem{ Hollan:Adapt} J.H.\ Holland: Adaptaion; Progress in theoretical biology, 4(1976)263-293

\bibitem{ Hoppe:Biophysik} W. Hoppe, W. Lohmann, H. Markl, H. Ziegler: Biophysik; Springer, 1978

\bibitem{ Kursaw:Vektor} F.\ Kursawe: A Variant of Evolution Strategies for Vector Optimization; PPSN 1990, Dortmund

\bibitem{ Muehle:EvoAlgs} H.\ M\"uhlenbein, M.\ Gorges-Schleuter, O.\ Kr\"amer: Evolution algorithms in combinatorial opimization; Parallel Computing 7(1988)65-85

\bibitem{ Muelle:EvoBeisp} K.D.\ M\"uller: Optimieren mit der Evolutionsstrategie in der Industrie anhand von Beispielen; Diss. TU Berlin, 1986

\bibitem{ Otto:SimAn} T. Otto: Reiselust --- Travelling Salesman, eine neue Strategie f\"ur eine alte Aufgabe; c't, 1(1994)188--194

\bibitem{ Poeppl:Funktional} J.\ P\"opplau: Funktionalminimierung mit Evolutionsstrategien unter Verwendung von finite Elemente Diskretisierungen; Mitteilung aus dem Institut f\"ur Str\"omungslehre und Str\"omungsmaschinen, Hochschule der Bundeswehr Hamburg, Heft Juli 1982

\bibitem{ Rechen:Evolut} I.\ Rechenberg: Evolutionsstrategie; Frommann-Holzboog, ISBN 3-7728-0-374

\bibitem{ Rechen:EvoDarw} I.\ Rechenberg: The evolution strategy. A mathematical model of Darwinian evolution; Berlin 1984

\bibitem{ Rechen:EvoStrat} I.\ Rechenberg: Evolution strategy: Nature's way of optimization; Lecture notes in Engineering, Vol. 47, Springer, 
Berlin 1989

\bibitem{ Rieck:ModellNatur} C. Rieck: Modell Natur --- Naturanaloge Verfahren in der Computersimulation; c't, 11(1993)201--208

\bibitem{ Riedel:Galvanik} H.J.\ Riedel: Einsatz rechnergest\"utzter Optimierung mittels der Evolutionsstrategie zur L\"osung galvanotechischer Probleme; Dissertation TU Berlin, 1984

\bibitem{ Handelsreis} G.\ Rudolph: Global Optimization by Means of 
Distributed Evolution Strategies; in H.-P.\ Schwefel und R.\ M\"anner (Hrsg.): 
Parallel Problem Solving from Nature, Lecture Notes in Computer Science 496, 
S.\ 209--213, Springer Verlag, 1991

\bibitem{ Schmie:Mikrowelle} H.\ Schmiedel: Anwendung der Evolutionsoptimierung bei Mikrowellenschaltungen; Frequenz 35(1981)306-310

\bibitem{ Schwef:Opti} H.-P.\ Schwefel: Numerische Optimierungs von Computermodellen mittels der Evolutionsstrategie; Interdisciplinary Systems Research 26, Birkh\"auser 1977

\bibitem{ Schwef:DirectSearch} H.-P.\ Schwefel: Direct Search for Optimal Parameters within Simulation Models; Proc.\ of the 12$^{\rm th}$ Annual Simulation Symposium, Tampa, Florida, 1979

\bibitem{ Schw88} H.-P.\ Schwefel: Evolutionary Learning Optimum-Seeking on 
Parallel Computer Architectures; in A.\ Sydow, S.G.\ Tzafestas, R.\ 
Vichnevetsky (Hrsg.): Proceedings of the International Symposium on Systems 
Analysis and Simulation 1988, I: Theory and Foundations, S.\ 217--225, 
Akademie-Verlag, Berlin, September 1988

\bibitem{ PPSN:1990} H.-P.\ Schwefel und R.\ M\"anner (Hrsg.): International 
Conference on ``Parallel Problem Solving from Nature'', Dortmund 1990; 
Lecture Notes in Computer Science 496, Springer Verlag, 1991

\bibitem{ Tschum:AllgBio} P.-A.\ Tschumi: Allgemeine Biologie; 
ISBN3-425-05659-X

\bibitem{ Zach} F. Zach: Technisches Optimieren; Springer, 1974, ISBN 0-387-81140-0
\end{thebibliography}

\end{document}